Intelligent Initialization and Adaptive Thresholding for Iterative Matrix Completion; Some Statistical and Algorithmic Theory for Adaptive-Impute

摘要

Over the past decade, various matrix completion algorithms have beendeveloped. Thresholded singular value decomposition (SVD) is a populartechnique in implementing many of them. A sizable number of studies have shownits theoretical and empirical excellence, but choosing the right thresholdlevel still remains as a key empirical difficulty. This paper proposes a novelmatrix completion algorithm which iterates thresholded SVD withtheoretically-justified and data-dependent values of thresholding parameters.The estimate of the proposed algorithm enjoys the minimax error rate and showsoutstanding empirical performances. The thresholding scheme that we use can beviewed as a solution to a non-convex optimization problem, understanding ofwhose theoretical convergence guarantee is known to be limited. We investigatethis problem by introducing a simpler algorithm, generalized-\SI, analyzing itsconvergence behavior, and connecting it to the proposed algorithm.